#include <iostream>
#include <string>
#include <stack>
#define MAX_VARIABLE_NUM 26
#define STACK_INIT_SIZE 128
#define STACK_INCREMENT 32
using namespace std;

typedef char TElemType;

typedef struct Node
{
    TElemType data;
    struct Node *lchild;
    struct Node *rchild;
} BTNode, BinaryTree;

typedef struct Stack
{
    Node **base;
    Node **top;
    int stacksize;
} SqStack;

void Exit(string message)
{
    cout << "ERROR:" << message << endl;
    exit(1);
}

//初始化栈
void InitSqStack(SqStack &S)
{
    S.base = (BTNode **)malloc(STACK_INIT_SIZE * sizeof(char));
    if (!S.base)
        Exit("Memory Deficiency");
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}

//弹出并返回栈顶元素
bool PopSqStack(Stack &S, BTNode *&e)
{
    if (S.top == S.base)
        return 0;
    e = *--S.top;
    return 1;
}

//入栈
void Push(Stack &S, BTNode *e)
{
    if (S.top - S.base >= S.stacksize)
    {
        S.base = (BTNode **)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(BTNode *));
        if (!S.base)
            Exit("Stack Overflow");
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *S.top++ = e;
}

//判断栈是否空，空的话返回1， 否则返回0
bool SqStackEmpty(Stack &S)
{
    if (S.base == S.top)
    {
        return 1;
    }
    return 0;
}

// Initialize Binary Tree
void InitBinaryTree(BTNode *&T)
{
    T = NULL;
}

void DestroyBinaryTree(BTNode *&T)
{
    if (T)
    {
        DestroyBinaryTree(T->lchild);
        DestroyBinaryTree(T->rchild);
        delete T;
    }
    T = NULL;
}

void PreOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        if (T->data)
            v(T, T->data);
        PreOrderTraverse(T->lchild, v);
        PreOrderTraverse(T->rchild, v);
    }
}
void InOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        PreOrderTraverse(T->lchild, v);
        if (T->data)
            v(T, T->data);
        PreOrderTraverse(T->rchild, v);
    }
}
void PostOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        PreOrderTraverse(T->lchild, v);
        PreOrderTraverse(T->rchild, v);
        if (T->data)
            v(T, T->data);
    }
}

bool JudgeSimbol(char &c)
{
    switch (c)
    {
    case '&':
    case '~':
    case '+':
    case '(':
    case ')':
        return true;
    default:
        return false;
    }
}

char Precede(char &t1, char &t2)
{
    char f;
    switch (t2)
    {
    case '+':
        if (t1 == '(')
            f = '<';
        else
            f = '>';
        break;
    case '*':
        if (t1 == '*' || t1 == ')')
            f = '>';
        else
            f = '<';
        break;
    case '~':
        if (t1 == '*' || t1 == '~' || t1 == ')')
            f = '>';
        else
            f = '<';
        break;
    case '(':
        f = '<';
        break;
    case ')':
        if (t1 == '(')
            f = '=';
        else
            f = '>';
        break;
    case '=':
        f = '>';
    }
    return f;
}

bool CreateBinaryExpTree(BinaryTree *&T, char ch[])
{
    SqStack OPND, OPTR;
    InitSqStack(OPND);
    InitSqStack(OPTR);
    BTNode *p, *q, *s;
    int i = 0, m;
    char theta;
    while (!SqStackEmpty(OPTR) || ch[i] != '=')
    {
        if (JudgeSimbol(ch[i]))
        {
            if (ch[i] == '+' && (i == 0 || ch[i - 1] == '('))
            {
                // 处理单目运算符
                p = new BTNode;
                p->data = 0;
                p->lchild = p->rchild = NULL;
                Push(OPND, p);
            }
            if (SqStackEmpty(OPTR))
            {
                q = new BTNode;
                q->data = ch[i];
                q->lchild = q->rchild = NULL;
                Push(OPTR, q);
                i++;
            }
            else if (!PopSqStack(OPTR, p))
            {
                theta = p->data;
                switch (Precede(theta, ch[i]))
                {
                case '<':
                    q = new Node;
                    q->data = ch[i];
                    q->lchild = q->rchild = NULL;
                    Push(OPTR, q);
                    i++;
                    break;
                case '=':
                    PopSqStack(OPTR, s);
                    i++;
                    break;
                case '>':
                    PopSqStack(OPTR, s);
                    if (SqStackEmpty(OPND))
                        return false;
                    PopSqStack(OPND, p);
                    if (SqStackEmpty(OPND))
                        return false;
                    PopSqStack(OPND, q);
                    s->lchild = q;
                    s->rchild = p;
                    Push(OPND, s);
                }
            }
        }
        else
            return false;
    }
    if (PopSqStack(OPND, T))
        return true;
    else
        return false;
}

bool Operate(bool map[MAX_VARIABLE_NUM], char a, char theta, char b = 0)
{
    bool c;
    switch (theta)
    {
    case '+':
        c = map[a - 'A'] + map[b - 'A'];
        break;
    case '~':
        c = !map[a - 'A'];
        break;
    case '*':
        c = map[a - 'A'] * map[b - 'A'];
    }
    return c;
}

char Evaluate(BTNode *&T, bool map[MAX_VARIABLE_NUM])
{
    if (T)
    {
        if (!T->lchild && !T->rchild)
            return T->data;
        return Operate(map, Evaluate(T->lchild, map), T->data, Evaluate(T->rchild, map));
    }
}

void DisplayExp(BTNode* &T, void(*visit)(BTNode*&T, char &e))
{
    char a, b;
    if(T)
    {
        if(T->lchild && T->lchild->lchild && (Precede(a=T->lchild->data, b=T->data) == '<'))
        {
            //根节点及它的左孩子结点都不是树叶
            //若左孩子结点的运算符优先级低则加括号
            cout << "(";
            DisplayExp(T->lchild, visit);
            cout << ")";
        }
        else
        {
            DisplayExp(T->lchild, visit);
        }
        if(T->data)
            visit(T, T->data);
        if(T->rchild && T->rchild->lchild && (Precede(a = T->rchild->data, b=T->data) == '<'))
        {
            cout << "(";
            DisplayExp(T->rchild, visit);
            cout << ")";
        }
        else
        {
            DisplayExp(T->rchild, visit);
        }
    }
}

void Print(BTNode* &T, TElemType &e)
{
    if(!T->lchild && !T->rchild)
        cout << e << "";
    else
    {
        char c = e;
        cout << c << " ";
    }
}

int main()
{
    BTNode* BT;
    char ch[256];
    char yes = 'y';
    do
    {
        InitBinaryTree(BT);
        cout << "随便输入个逻辑表达式" << endl;
        cin >> ch;
        cout << endl;

        if(CreateBinaryExpTree(BT, ch))
        {
            cout << "表达式的前缀表示为：" << endl;
            PreOrderTraverse(BT, Print);
            cout << endl;

            cout << "表达式的中缀表示为：" << endl;
            InOrderTraverse(BT, Print);
            cout << endl;

            cout << "表达式的后缀表示为：" << endl;
            PostOrderTraverse(BT, Print);
            cout << endl;

            cout << "表达式为：" << endl;
            DisplayExp(BT, Print);
        }
        else
        {
            cout << "表达式输入有误！" << endl;
        }
        cout << "继续？" << endl;
        cin >> yes;
        cout << endl;
        DestroyBinaryTree(BT);

    }while(yes == 'y');
}